package com.gxc.sort;

import com.gxc.randomArray.generateRandomArray;

/**
 * Created by ASD on 2023/6/5.
 */
public class radix {

    public static void main(String[] args) {
        int[] arr = generateRandomArray.generateArray2(20, 30);
        //arr = new int[]{10   , 24  ,  25   , 2   , 14    };

        generateRandomArray.sout(arr);

        int maxbit = maxbit(arr);
        radixSort(arr,0 , arr.length-1, maxbit);

        System.out.println("=======排序后=====");

        generateRandomArray.sout(arr);
    }

    private static void radixSort(int[] arr, int l, int r, int maxbit) {
        final int radix = 10;

        int[] help = new int[r-l+1];
        for (int d=1;d<=maxbit;d++) {
            int[] barrel = new int[radix];
            for (int i = l; i <= r; i++) {
                barrel[getDigit(arr[i], d, radix)]++;
            }

            for (int i = 1; i < barrel.length; i++) {
                barrel[i] = barrel[i] + barrel[i-1];
            }
            //出桶
            for (int i = r; i >=l; i--) {
                help[--barrel[getDigit(arr[i], d, radix)]]=arr[i];
            }

            for (int i = l; i <= r; i++) {
                arr[i] = help[i];
            }
        }
    }

    private static int getDigit(int arr, int d, int radix) {
        if (d ==1) {
            return arr%radix;
        }
        int radix2 = radix;
        for (int i=3;i<=d;i++) {
            radix2 = radix2 * radix;
        }
        return arr/radix2;
    }

    private static int maxbit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }

        int digit = 0;
        while (max!=0) {
            digit++;
            max = max/10;
        }
        return digit;
    }

}
